package ee.project.binarytree;

import ee.project.Stopwatch;

public class BinarySearchTree {

	private BinaryNode root;

	public BinarySearchTree() {
		root = null;
	}

	public static void main(String[] args) {
		BinarySearchTree t = new BinarySearchTree();
		final int NUMS = 10000;
		final int GAP = 37;

		System.out.println("Arbitrary adding, decremental removing");
		Stopwatch timer = new Stopwatch().start();
		for (int i = GAP; i != 0; i = (i + GAP) % NUMS) {
			t.insert(new Integer(i));
		}
		timer.stop();
		System.out.println("Insert time: " + timer.getTimeElapsed() + " ms");

		timer.reset().start();
		for (int i = NUMS - 1; i >= 0; i--) {
			t.remove(new Integer(i));
		}
		timer.stop();
		System.out.println("Remove time: " + timer.getTimeElapsed() + " ms");
		System.out.println();

		// 
		System.out.println("Arbitrary adding, incremental removing");
		timer.reset().start();
		for (int i = GAP; i != 0; i = (i + GAP) % NUMS) {
			t.insert(new Integer(i));
		}
		timer.stop();
		System.out.println("Insert time: " + timer.getTimeElapsed() + " ms");

		timer.reset().start();
		for (int i = 0; i < NUMS; i++) {
			t.remove(new Integer(i));
		}
		timer.stop();
		System.out.println("Remove time: " + timer.getTimeElapsed() + " ms");
		System.out.println();

		//
		System.out.println("Arbitrary adding, arbitrary removing");
		timer.reset().start();
		for (int i = GAP; i != 0; i = (i + GAP) % NUMS) {
			t.insert(new Integer(i));
		}
		timer.stop();
		System.out.println("Insert time: " + timer.getTimeElapsed() + " ms");

		timer.reset().start();
		for (int i = GAP; i != 0; i = (i + GAP) % NUMS) {
			t.remove(new Integer(i));
		}
		timer.stop();
		System.out.println("Remove time: " + timer.getTimeElapsed() + " ms");
		System.out.println();

		//
		System.out.println("Incremental adding, incremental removing");
		timer.reset().start();
		for (int i = 0; i < NUMS; i++) {
			t.insert(new Integer(i));
		}
		timer.stop();
		System.out.println("Insert time: " + timer.getTimeElapsed() + " ms");

		timer.reset().start();
		for (int i = 0; i < NUMS; i++) {
			t.remove(new Integer(i));
		}
		timer.stop();
		System.out.println("Remove time: " + timer.getTimeElapsed() + " ms");
		System.out.println();

		//
		System.out.println("Incremental adding, decremental removing");
		timer.reset().start();
		for (int i = 0; i < NUMS; i++) {
			t.insert(new Integer(i));
		}
		timer.stop();
		System.out.println("Insert time: " + timer.getTimeElapsed() + " ms");

		timer.reset().start();
		for (int i = NUMS - 1; i >= 0; i--) {
			t.remove(new Integer(i));
		}
		timer.stop();
		System.out.println("Remove time: " + timer.getTimeElapsed() + " ms");
		System.out.println();

		//
		System.out.println("Incremental adding, arbitrary removing");
		timer.reset().start();
		for (int i = 0; i < NUMS; i++) {
			t.insert(new Integer(i));
		}
		timer.stop();
		System.out.println("Insert time: " + timer.getTimeElapsed() + " ms");

		timer.reset().start();
		for (int i = GAP; i != 0; i = (i + GAP) % NUMS) {
			t.remove(new Integer(i));
		}
		timer.stop();
		System.out.println("Remove time: " + timer.getTimeElapsed() + " ms");
		System.out.println();

		//
		System.out.println("Decremental adding, incremental removing");
		timer.reset().start();
		for (int i = NUMS - 1; i >= 0; i--) {
			t.insert(new Integer(i));
		}
		timer.stop();
		System.out.println("Insert time: " + timer.getTimeElapsed() + " ms");

		timer.reset().start();
		for (int i = 0; i < NUMS; i++) {
			t.remove(new Integer(i));
		}
		timer.stop();
		System.out.println("Remove time: " + timer.getTimeElapsed() + " ms");
		System.out.println();

		//
		System.out.println("Decremental adding, abitrary removing");
		timer.reset().start();
		for (int i = NUMS - 1; i >= 0; i--) {
			t.insert(new Integer(i));
		}
		timer.stop();
		System.out.println("Insert time: " + timer.getTimeElapsed() + " ms");

		timer.reset().start();
		for (int i = GAP; i != 0; i = (i + GAP) % NUMS) {
			t.remove(new Integer(i));
		}
		timer.stop();
		System.out.println("Remove time: " + timer.getTimeElapsed() + " ms");
		System.out.println();

		//
		System.out.println("Decremental adding, decremental removing");
		timer.reset().start();
		for (int i = NUMS - 1; i >= 0; i--) {
			t.insert(new Integer(i));
		}
		timer.stop();
		System.out.println("Insert time: " + timer.getTimeElapsed() + " ms");

		timer.reset().start();
		for (int i = NUMS - 1; i >= 0; i--) {
			t.remove(new Integer(i));
		}
		timer.stop();
		System.out.println("Remove time: " + timer.getTimeElapsed() + " ms");
	}

	public void insert(Comparable x) {
		root = insert(x, root);
	}

	public void remove(Comparable x) {
		root = remove(x, root);
	}

	public Comparable findMin() {
		return elementAt(findMin(root));
	}

	public Comparable findMax() {
		return elementAt(findMax(root));
	}

	public Comparable find(Comparable x) {
		return elementAt(find(x, root));
	}

	public void makeEmpty() {
		root = null;
	}

	public boolean isEmpty() {
		return root == null;
	}

	public void printTree() {
		if (isEmpty())
			System.out.println("Empty tree");
		else
			printTree(root);
	}

	private Comparable elementAt(BinaryNode t) {
		return t == null ? null : t.element;
	}

	private BinaryNode insert(Comparable x, BinaryNode t) {
		if (t == null)
			t = new BinaryNode(x, null, null);
		else if (x.compareTo(t.element) < 0)
			t.left = insert(x, t.left);
		else if (x.compareTo(t.element) > 0)
			t.right = insert(x, t.right);
		else
			;
		return t;
	}

	private BinaryNode remove(Comparable x, BinaryNode t) {
		if (t == null)
			return t;
		if (x.compareTo(t.element) < 0)
			t.left = remove(x, t.left);
		else if (x.compareTo(t.element) > 0)
			t.right = remove(x, t.right);
		else if (t.left != null && t.right != null) {
			t.element = findMin(t.right).element;
			t.right = remove(t.element, t.right);
		} else
			t = (t.left != null) ? t.left : t.right;
		return t;
	}

	private BinaryNode findMin(BinaryNode t) {
		if (t == null)
			return null;
		else if (t.left == null)
			return t;
		return findMin(t.left);
	}

	private BinaryNode findMax(BinaryNode t) {
		if (t != null)
			while (t.right != null)
				t = t.right;

		return t;
	}

	private BinaryNode find(Comparable x, BinaryNode t) {
		if (t == null)
			return null;
		if (x.compareTo(t.element) < 0)
			return find(x, t.left);
		else if (x.compareTo(t.element) > 0)
			return find(x, t.right);
		else
			return t;
	}

	private void printTree(BinaryNode t) {
		if (t != null) {
			printTree(t.left);
			System.out.print(t.element + " ");
			printTree(t.right);
		}
	}
}
